package sword_offer;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Synhard
 * @version 1.0
 * @class Code48
 * @description 剑指 Offer 34. 二叉树中和为某一值的路径
 * 输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
 *
 *  
 *
 * 示例:
 * 给定如下二叉树，以及目标和 target = 22，
 *
 *               5
 *              / \
 *             4   8
 *            /   / \
 *           11  13  4
 *          /  \    / \
 *         7    2  5   1
 * 返回:
 *
 * [
 *    [5,4,11,2],
 *    [5,8,4,5]
 * ]
 *  
 *
 * 提示：
 *
 * 节点总数 <= 10000
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-07-10 8:59
 */
public class Code48 {
    public static void main(String[] args) {

    }

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(root, res, path, 0, target);
        return res;
    }

    public void dfs(TreeNode root, List<List<Integer>> res, List<Integer> path, int sum, int target) {
        if (root == null) {
            return;
        }
        path.add(root.val);
        if (root.val + sum == target && root.left == null && root.right == null) { // 这个条件必须是到叶子节点的约束
            List<Integer> tmp = new ArrayList<>(path);
            res.add(tmp);
        }
        dfs(root.left, res, path, sum + root.val, target);
        dfs(root.right, res, path, sum + root.val, target);
        path.remove(path.size() - 1);
    }
}
